package BinaryTreeExer;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏李涛
 * Date: 2024-07-20
 * Time: 10:38
 */

/**
 * 相同的树:
 *
 * 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
 *
 * 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：p = [1,2,3], q = [1,2,3]
 * 输出：true
 * 示例 2：
 *
 *
 * 输入：p = [1,2], q = [1,null,2]
 * 输出：false
 * 示例 3：
 *
 *
 * 输入：p = [1,2,1], q = [1,1,2]
 * 输出：false
 */


/**
 如果设q 有n个节点，p有m个节点
 时间复杂度为 0(min(n,m)), m和n的最小值
 */

public class BinaryTreeExercise1 {

    static class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode(int val) { this.val = val; }
       TreeNode(int val, TreeNode left, TreeNode right) {
           this.val = val;
       }
   }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        //先判断结构是否一样
        if(p != null && q == null || q != null && p == null) {
            return false;
        }
        //走到这里，两个都为空或者两个都不为空

        //排除都为空树，但是空树也是树
        if(p == null && q == null) {
            return true;
        }
        //走到这里两个都不为空

        //开始判断树，根的值是否一样
        if(p.val != q.val) {
            return false;
        }

        //树都不为空，树根的值一样就判断：左子树 && 右边是否一样

        if(isSameTree(p.left, q.left)
                && isSameTree(p.right, q.right)) {
            return true;
        }

        return false;
    }
}
